//给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。 
//
// 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： 
//
// 
// "123" 
// "132" 
// "213" 
// "231" 
// "312" 
// "321" 
// 
//
// 给定 n 和 k，返回第 k 个排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3, k = 3
//输出："213"
// 
//
// 示例 2： 
//
// 
//输入：n = 4, k = 9
//输出："2314"
// 
//
// 示例 3： 
//
// 
//输入：n = 3, k = 1
//输出："123"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 1 <= k <= n! 
// 
// Related Topics 数学 回溯算法 
// 👍 538 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PermutationSequence {
    public static void main(String[] args) {
        Solution solution = new PermutationSequence().new Solution();
        System.out.println(solution.getPermutation(3, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private StringBuilder path = new StringBuilder();
        private int[] visit;
        private int target;
        private int k=0;
        private String res;

        public String getPermutation(int n, int k) {
            target=k;
            visit = new int[n+1];
            dfs(n);
            return res;
        }


        public void dfs(int n) {
            if (path.length()==n){
                k++;
                if (k==target){
                    res = path.toString();
                }
                return;
            }
            for (int i = 1; i < n+1; i++) {
                if(visit[i]==1){
                    continue;
                }
                visit[i]=1;
                path.append(i);
                dfs(n);
                path.deleteCharAt(path.length()-1);
                visit[i]=0;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}